# n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
#
#
#
#  上图为 8 皇后问题的一种解法。
#
#  给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
#
#  每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
#
#
#
#  示例：
#
#  输入：4
# 输出：[
#  [".Q..",  // 解法 1
#   "...Q",
#   "Q...",
#   "..Q."],
#
#  ["..Q.",  // 解法 2
#   "Q...",
#   "...Q",
#   ".Q.."]
# ]
# 解释: 4 皇后问题存在两个不同的解法。
#
#
#
#
#  提示：
#
#
#  皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
#
#  Related Topics 回溯算法
#  👍 528 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        # 对角线，斜对角线，列 ，初始多可以放置
        diagonal = [True] * (2*n-1)
        cdiagonal = [True] * (2*n-1)
        col = [True] * n
        tmp = []
        res = []

        def helper(row, n):
            nonlocal diagonal, cdiagonal, col, tmp, res

            if row == n:
                res.append(tmp[:])

                return

            for i in range(0, n):
                if col[i] and diagonal[i - row] and cdiagonal[row + i]:
                    col[i] = False
                    diagonal[i - row] = False
                    cdiagonal[i + row] = False
                    tmp.append(i)
                    helper(row + 1, n)
                    col[i] = True
                    diagonal[i - row] = True
                    cdiagonal[i + row] = True
                    tmp.pop()

        helper(0, n)

        solutions = []
        for positions in res:

            solution = []
            for pos in positions:
                solution.append('.' * pos + 'Q' + '.' * (n - 1 - pos))
            solutions.append(solution)
        return solutions
# leetcode submit region end(Prohibit modification and deletion)


print(Solution().solveNQueens(4))